import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 东莞呵呵
 * Date:2022-06-21
 * Time:15:25
 */
public class QuickSort {
    public static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }

    public static void quick(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int partition = partition(array, start, end);
        quick(array, start, partition - 1);
        quick(array, partition + 1, end);
    }

    public static int partition(int[] array, int start, int end) {
        int tmp = array[start];
        while (start < end) {

            while (end > start && array[end] >= tmp) {//必须有=
                end--;
            }
            array[start] = array[end];
            while (end > start && array[start] <= tmp) {
                start++;
            }
            array[end] = array[start];
        }
        array[start]=tmp;
        return start;
    }

    public static void main(String[] args) {
        int[] arr = {65, 43, 5, 7, 4, 5, 76, 23, 4, 765, 42, 6, 7, 8};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
